package cn.anquing.datastructure.sort;

import java.util.Comparator;

/**
 * 冒泡实现类,选择排序，时间复杂度O(n^2)
 *
 * @author wangquanqing
 * @since 2021/3/24 14:34
 */
public class BubbleSorter implements ISort {

    @Override
    public  void sortInt(Integer[] list) {
        final int n = list.length;
        // 如果数组已排好了序就停止
        boolean swapped = true;
        for (int i = 1; i < n && swapped; ++i) {
            swapped = false;
            for( int j = 0; j < n-i; ++j) {
                if (list[j]>(list[j+1])) {
                    // 交换位置
                    // 1.辅助空间⽅法
//                    Integer temp = list[j];
//                    list[j] = list[j+1];
//                    list[j+1] = temp;

                    // 2.位异或运算（^）,利⽤位异或运算(^)节省辅助空间，降低空间复杂度
                    list[j] =  list[j] ^ list[j + 1];
                    list[j + 1] = list[j] ^ list[j + 1];
                    list[j] = list[j] ^ list[j + 1];
                    swapped = true;
                }
            }
        }
    }

    public  <T extends Comparable> void sort(T[] list) {

        final int n = list.length;
        // 如果数组已排好了序就停止
        boolean swapped = true;
        for (int i = 1; i < n && swapped; ++i) {
            swapped = false;
            for( int j = 0; j < n-i; ++j) {
                if (list[j].compareTo(list[j+1])> 0) {
                    // 大的往后挪
                    T temp = list[j];
                    list[j] = list[j+1];
                    list[j+1] = temp;

                    // 位异或运算（^）


                    swapped = true;
                }
            }
        }
    }

    public  <T> void sort(T[] list, Comparator<T> comparator) {
        final int n = list.length;
        // 如果数组已排好了序就停止
        boolean swapped = true;
        for (int i = 1; i < n && swapped; ++i) {
            swapped = false;
            for( int j = 0; j < n-i; ++j) {
                if (comparator.compare(list[j],list[j+1])> 0) {
                    // 大的往后挪
                    T temp = list[j];
                    list[j] = list[j+1];
                    list[j+1] = temp;
                    swapped = true;
                }
            }
        }
    }
}
